public class Solution25 {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1)
            return head;
        head = new ListNode(0, head);
        ListNode p = head, q = head.next;

        while (q != null) {
            int n = 1;
            while (q != null) {
                q = q.next;
                n++;
                if (n == k) {
                    break;
                }
            }
            if (q == null)
                break;
            q = q.next;
            p = reverse(p, p.next, 1, k);
            p.next = q;
        }

        return head.next;
    }

    //倒转从first结点开始的n个节点，返回倒转后的最后一个结点，cur表示当前位置，head为头结点，指向第一个结点
    private ListNode reverse(ListNode head, ListNode first, int cur, int n) {
        if (cur == n) {
            head.next = first;
            return first;
        }
        ListNode t = reverse(head, first.next, cur + 1, n);
        t.next = first;
        return first;
    }
}
